class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1
            return True
        return False


def kruskal(num_vertices, edges):
    # 对边按权值从小到大排序
    edges.sort(key=lambda x: x[2])
    mst = []
    uf = UnionFind(num_vertices)
    for u, v, w in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
            if len(mst) == num_vertices - 1:
                break
    return mst


# 示例使用
num_vertices = 4
edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
mst = kruskal(num_vertices, edges)
print("最小生成树的边:", mst)
total_weight = sum([w for _, _, w in mst])
print("最小生成树的总权值:", total_weight)